'''
选择排序是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
算法步骤：
在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
示例（升序排序）：
假设有一个数组 arr = [64, 25, 12, 22, 11]，选择排序的过程如下：
初始状态：未排序序列 [64, 25, 12, 22, 11]，已排序序列为空。
第一轮选择：找到最小元素 11，与未排序序列的第一个元素 64 交换，得到 [11, 25, 12, 22, 64]。
第二轮选择：在未排序序列 [25, 12, 22, 64] 中找到最小元素 12，与未排序序列的第一个元素 25 交换，得到 [11, 12, 25, 22, 64]。
重复上述过程，直到整个数组排序完成。
时间复杂度分析
最好情况：时间复杂度为 O(n^2 )。即使输入数组已经是排序好的，选择排序仍然需要比较每个元素来找到最小（或最大）的元素。
最坏情况：时间复杂度为 O(n^2 )。对于完全逆序的数组，选择排序需要执行最多的比较和交换操作。
平均情况：时间复杂度同样是 O(n^2 )。
空间复杂度分析
选择排序的空间复杂度为 O(1)。因为它是一种原地排序算法，只需要固定的额外空间来存储临时变量（如最小元素的索引），不随输入规模的变化而变化。
总结
选择排序不是稳定性排序，相等的元素可能会交换位置，虽然简单，但其效率较低，不适合对大数据集进行排序。然而，由于其实现简单且不需要额外的存储空间（除了几个临时变量），
在某些特定场景下仍然有其应用价值。
'''
class Solution:
    def selectionSort(self, arr):
        n = len(arr)
        for i in range(n):
            min_index = i   #初始化最小index
            for j in range(i+1, n):
                if arr[j] < arr[min_index]:
                    min_index = j
            if i != min_index:
                arr[i], arr[min_index] = arr[min_index], arr[i]     #交换最小值到下标i的位置
        return arr
#示例
if __name__ == '__main__':
    arr = [64, 25, 12, 22, 11]
    print(Solution().selectionSort(arr))